# LeetCode 5、最长回文子串
# 一、题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
提示：
1 <= s.length <= 1000s仅由数字和英文字母（大写和/或小写）组成
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最长回文子串（ LeetCode 5 ）：https://leetcode-cn.com/problems/longest-palindromic-substring/
class Solution {
public String longestPalindrome(String s) {
// 获取字符串 s 的长度
int length = s.length();
// 设置数组 dp，用来存储字符串 s 的 [i,j] 区间的子串是否是回文子串
// dp[0][0] 表示字符串 s 第 0 个字符和字符串 s 第 0 个字符之间的子串是否是回文子串
// dp[2][3] 表示字符串 s 第 2 个字符和字符串 s 第 3 个字符之间的子串是否是回文子串
// dp[i][j] 表示字符串 s 第 i 个字符和字符串 s 第 j 个字符之间的子串是否是回文子串
// i 最大值为 length - 1
boolean[][] dp = new boolean[length][ length];
// dp[0][0] 表示字符串 s 第 0 个字符和字符串 s 第 0 个字符之间的的子串是否是回文子串
// dp[3][3] 表示字符串 s 第 3 个字符和字符串 s 第 3 个字符之间的的子串是否是回文子串
// dp[i][i] 表示字符串 s 第 i 个字符和字符串 s 第 i 个字符之间的的子串是否是回文子串
// 此时，这个区间的字符只有一个，肯定是回文子串
for (int i = 0; i < length; i++) {
dp[i][i] = true;
}
// 设置变量记录最长的回文子串的长度
int maxLen = 1;
// 设置变量记录最长的回文子串的开始位置
// 从后向前寻找
int begin = length - 1;
// i 从字符串 s 的【尾部】开始向前遍历，j 从 i + 1 开始向后遍历
// 不断的逼近二维数组最右上角的位置，即求 dp[0][length - 1]
for (int i = length - 1; i >= 0; i--) {
for( int j = i + 1 ; j < length ; j++ ){
// 如果发现 s.charAt(i) == s.charAt(j)
if (s.charAt(i) == s.charAt(j)) {
// 如果 [i , j] 这个区间中只有 2 个字符，并且此时两个字符还是一样的
// 那么肯定是回文子串
// 假设 i = 5， j = 6，[i , j] 这个区间中只有 2 个字符
// 如果不加这个判断的话，dp[i][j] = dp[ i + 1 ][ j - 1 ]
// 此时，i + 1 = 6， j - 1 = 5
// [ 6 , 5 ] 这个区间不存在，默认值为 false
if( (j - i + 1) == 2){
dp[i][j] = true;
}else{
// 否则，当前这个区间是否是回文子串区间取决于 [ i + 1 , j - 1 ] 这个区间
dp[i][j] = dp[ i + 1 ][ j - 1 ];
}
}else{
// 如果发现 s.charAt(i) ！= s.charAt(j)
// 那说明 [i , j] 这个区间必然不是回文子串
dp[i][j] = false;
}
// 更新最长的回文子串长度
if(dp[i][j] && j - i + 1 > maxLen){
// 更新最长的回文子串长度
maxLen = j - i + 1;
// 更新最长的回文子串的开始位置
begin = i;
}
}
}
// 通过截取的方式返回最长的回文子串
// Java substring() 方法
// beginIndex -- 起始索引（包括）, 索引从 0 开始
// endIndex -- 结束索引（不包括）
// 0 1 2 3 4
// b a b a d
// 此时，begin = 1，maxLen = 3
// substring( 1 , 4 )，即截取 [1 , 4 ) ，左闭右开的区间
// 获取子串 aba
return s.substring(begin, begin + maxLen);
}
}
# **2、**C++ 代码
class Solution {
public:
string longestPalindrome(string s) {
// 获取字符串 s 的长度
int length = s.length();
// 设置数组 dp，用来存储字符串 s 的 [i,j] 区间的子串是否是回文子串
// dp[0][0] 表示字符串 s 第 0 个字符和字符串 s 第 0 个字符之间的子串是否是回文子串
// dp[2][3] 表示字符串 s 第 2 个字符和字符串 s 第 3 个字符之间的子串是否是回文子串
// dp[i][j] 表示字符串 s 第 i 个字符和字符串 s 第 j 个字符之间的子串是否是回文子串
// i 最大值为 length - 1
auto dp = vector < vector < bool>> ( length ,vector<bool> ( length ));
// dp[0][0] 表示字符串 s 第 0 个字符和字符串 s 第 0 个字符之间的的子串是否是回文子串
// dp[3][3] 表示字符串 s 第 3 个字符和字符串 s 第 3 个字符之间的的子串是否是回文子串
// dp[i][i] 表示字符串 s 第 i 个字符和字符串 s 第 i 个字符之间的的子串是否是回文子串
// 此时，这个区间的字符只有一个，肯定是回文子串
for (int i = 0; i < length; i++) {
dp[i][i] = true;
}
// 设置变量记录最长的回文子串的长度
int maxLen = 1;
// 设置变量记录最长的回文子串的开始位置
// 从后向前寻找
int begin = length - 1;
// i 从字符串 s 的【尾部】开始向前遍历，j 从 i + 1 开始向后遍历
// 不断的逼近二维数组最右上角的位置，即求 dp[0][length - 1]
for (int i = length - 1; i >= 0; i--) {
for( int j = i + 1 ; j < length ; j++ ){
// 如果发现 s.charAt(i) == s.charAt(j)
if (s[i] == s[j]) {
// 如果 [i , j] 这个区间中只有 2 个字符，并且此时两个字符还是一样的
// 那么肯定是回文子串
// 假设 i = 5， j = 6，[i , j] 这个区间中只有 2 个字符
// 如果不加这个判断的话，dp[i][j] = dp[ i + 1 ][ j - 1 ]
// 此时，i + 1 = 6， j - 1 = 5
// [ 6 , 5 ] 这个区间不存在，默认值为 false
if( (j - i + 1) == 2){
dp[i][j] = true;
}else{
// 否则，当前这个区间是否是回文子串区间取决于 [ i + 1 , j - 1 ] 这个区间
dp[i][j] = dp[ i + 1 ][ j - 1 ];
}
}else{
// 如果发现 s.charAt(i) ！= s.charAt(j)
// 那说明 [i , j] 这个区间必然不是回文子串
dp[i][j] = false;
}
// 更新最长的回文子串长度
if(dp[i][j] && j - i + 1 > maxLen){
// 更新最长的回文子串长度
maxLen = j - i + 1;
// 更新最长的回文子串的开始位置
begin = i;
}
}
}
// 通过截取的方式返回最长的回文子串
// Java substring() 方法
// beginIndex -- 起始索引（包括）, 索引从 0 开始
// endIndex -- 结束索引（不包括）
// 0 1 2 3 4
// b a b a d
// 此时，begin = 1，maxLen = 3
// substring( 1 , 4 )，即截取 [1 , 4 ) ，左闭右开的区间
// 获取子串 aba
return s.substr(begin, maxLen);
}
};
# 3、Python 代码
class Solution:
def longestPalindrome(self, s: str) -> str:
# 获取字符串 s 的长度
length = len(s)
# 设置数组 dp，用来存储字符串 s 的 [i,j] 区间的子串是否是回文子串
# dp[0][0] 表示字符串 s 第 0 个字符和字符串 s 第 0 个字符之间的子串是否是回文子串
# dp[2][3] 表示字符串 s 第 2 个字符和字符串 s 第 3 个字符之间的子串是否是回文子串
# dp[i][j] 表示字符串 s 第 i 个字符和字符串 s 第 j 个字符之间的子串是否是回文子串
# i 最大值为 length - 1
dp = [[False] * length for _ in range(length)]
# dp[0][0] 表示字符串 s 第 0 个字符和字符串 s 第 0 个字符之间的的子串是否是回文子串
# dp[3][3] 表示字符串 s 第 3 个字符和字符串 s 第 3 个字符之间的的子串是否是回文子串
# dp[i][i] 表示字符串 s 第 i 个字符和字符串 s 第 i 个字符之间的的子串是否是回文子串
# 此时，这个区间的字符只有一个，肯定是回文子串
for i in range(length):
dp[i][i] = True
# 设置变量记录最长的回文子串的长度
maxLen = 1
# 设置变量记录最长的回文子串的开始位置
# 从后向前寻找
begin = length - 1
# i 从字符串 s 的【尾部】开始向前遍历，j 从 i + 1 开始向后遍历
# 不断的逼近二维数组最右上角的位置，即求 dp[0][length - 1]
for i in range( length - 1 , -1 , -1 ):
for j in range( i + 1 , length ):
# 如果发现 s.charAt(i) == s.charAt(j)
if s[i] == s[j]:
# 如果 [i , j] 这个区间中只有 2 个字符，并且此时两个字符还是一样的
# 那么肯定是回文子串
# 假设 i = 5， j = 6，[i , j] 这个区间中只有 2 个字符
# 如果不加这个判断的话，dp[i][j] = dp[ i + 1 ][ j - 1 ]
# 此时，i + 1 = 6， j - 1 = 5
# [ 6 , 5 ] 这个区间不存在，默认值为 false
if (j - i + 1) == 2 :
dp[i][j] = True
else:
# 否则，当前这个区间是否是回文子串区间取决于 [ i + 1 , j - 1 ] 这个区间
dp[i][j] = dp[ i + 1 ][ j - 1 ]
else:
# 如果发现 s.charAt(i) ！= s.charAt(j)
# 那说明 [i , j] 这个区间必然不是回文子串
dp[i][j] = False
# 更新最长的回文子串长度
if dp[i][j] and j - i + 1 > maxLen :
# 更新最长的回文子串长度
maxLen = j - i + 1
# 更新最长的回文子串的开始位置
begin = i
# 通过截取的方式返回最长的回文子串
return s[begin:begin + maxLen]